package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.PrinterUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * 2-opt
 */
public class Ls2opt extends LocalSearch {


    public Ls2opt(Problem problem) {
        super(problem);
    }

    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("local search 2opt init", initSolution);
        Solution finalSolution = improve(initSolution);
        PrinterUtils.printTspResult("local search 2opt final", finalSolution);
    }

    @Override
    public Solution improve(Solution solution) {
        List<Integer> permutation = solution.getPermutation();
        int n = permutation.size();
        int bestCost = solution.getCost();
        for (int i = 1; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                List<Integer> newPermutation = new ArrayList<>(permutation.subList(0, i));
                newPermutation.addAll(reverse(permutation.subList(i, j + 1)));
                newPermutation.addAll(permutation.subList(j + 1, n));
                int cost = calculateFitness(newPermutation);
                if (cost < bestCost) {
                    bestCost = cost;
                    permutation = newPermutation;
                }
            }
        }
        return new Solution(permutation, bestCost);
    }

    private List<Integer> reverse(List<Integer> s) {
        List<Integer> r = new ArrayList<>();
        for (int i = 0; i < s.size(); i++) {
            r.add(s.get(s.size() - 1 - i));
        }
        return r;
    }

}
